package com.tool.cn.use;
/**
 * 多种排序
 * 
 * @author wangzh
 * 2017年3月16日 下午2:57:02
 */
public class SortNum {


	/**
	 * 插入排序
	 * 
	 * 构造有序序列，在已排序序列中从后向前扫描，找到相应位置插入
	 */
	public static void insertSort(int[] numbers){
		int size=numbers.length,temp,j;
		for(int i=1;i<size;i++){
			temp=numbers[i];
			for(j=1;j>0&&temp<numbers[j-1];j--)
				numbers[j]=numbers[j-1];
			numbers[j]=temp;
		}
	}
	
	/**
	 * 冒泡排序
	 * 
	 * 比较相邻的元素，如果第一个比第二个大，交换他们两个
	 * 针对所有元素重复以上步骤
	 */
	public static void bubbleSort(int[] numbers){
		int temp;//记录临时中间值
		int size=numbers.length;
		for(int i=0;i<size-1;i++){
			for(int j=i+1;j<size;j++){
				if(numbers[i]<numbers[j]){//交换位置
					temp=numbers[i];
					numbers[i]=numbers[j];
					numbers[j]=temp;
				}
			}
		}
	}
	
	/**
	 * 选择排序
	 * 
	 * 在未排序序列中，找出最小元素，存放到排序序列的起始位置
	 */
	public static void selectSort(int [] numbers){
		int size=numbers.length,temp;
		for(int i=0;i<size;i++){
			int k=i;
			for(int j=size-1;j>i;j--){
				if(numbers[j]<numbers[k])
					k=j;
			}
			temp=numbers[i];
			numbers[i]=numbers[k];
			numbers[k]=temp;
		}
		
	}
	
	/**
	 * Shell排序
	 * 
	 * 希尔排序 
	 *  希尔排序(缩小增量法) 属于插入类排序，
	 *  是将整个无序列分割成若干小的子序列分别进行插入排序。希尔排序并不稳定，O(1)的额外空间，时间复杂度为O(N*(logN)^2)
	 */
	public static void shallSort(int[] numbers){
		int h=1; //计算最大的h的值
		while(h<=numbers.length/3){
			h=h*3+1; 
		}
		while(h>0){
			for(int i=h;i<numbers.length;i+=h){
				if(numbers[i]<numbers[i-h]){
					int tmp=numbers[i];
					int j=i-h;
					while(j>=0&&numbers[j]>tmp){
						numbers[j+h]=numbers[j];
						j-=h;
					}
					numbers[j+h]=tmp;
					
				}
			}
			//计算出下一个h的值
			h=(h-1)/3;
		}
	}
	
	/**
	 * 快速排序
	 * 
	 * 从数列中挑出一个元素为基数，重新排序数列，比基数小的摆在基数前，大的在基数后面
	 * 这称作分割操作
	 * 递归地把小于基数和大于基数的子数列排序
	 */
	public static void quickSort(int[] numbers,int start,int end){
		if(start<end){
			int base=numbers[start];//选定的准基数（第一个作为基准数）
			int temp;//记录临时中间值
			int i=start,j=end;
			
			do{
				while((numbers[i]<base)&&(i<end))
					i++;
				while((numbers[j]>base)&&(j>start))
					j--;
				if(i<=j){
					temp=numbers[i];
					numbers[i]=numbers[j];
					numbers[j]=temp;
					i++;
					j--;
				}
			}while(i<=j);
			if(start<j)
				quickSort(numbers,start,j);
			if(end>i)
				quickSort(numbers,i,end);
		}
	}
	
	/**
	 * 归并排序
	 * 
	 * 将已经排序的序列合并成一个序列的操作
	 */
	public static void mergeSort(int[] numbers,int left,int right){
		int t=1;//每组元素个数
		int size=right-left+1;
		while(t<size){
			int s=t;//本次循环每组元素个数
			t=2*s;
			int i=left;
			while(i+(t-1)<size){
				merge(numbers,i,i+(s-1),i+(t-1));
				i+=t;
			}
			if(i+(s-1)<right)
				merge(numbers,i,i+(s-1),right);
		}
	}
	
	//并归算法实现
	private static void merge(int[] data,int p,int q,int r){
		int[] B=new int[data.length];
		int s=p;
		int t=q+1;
		int k=p;
		while(s<=q&&t<=r){
			if(data[s]<=data[t]){
				B[k]=data[s];
				s++;
			}else{
				B[k]=data[t];
				t++;
			}
			k++;
		}
		
		if(s==q+1)
			B[k++]=data[t++];
		else
			B[k++]=data[s++];
		for(int i=p;i<=r;i++)
			data[i]=B[i];
	}
	
	/**
	 * 堆排序
	 * 
	 * 堆排序是不稳定的排序算法，辅助空间为O(1),最坏时间复杂度O(nlog2n),堆排序的堆序的平均性能接近最坏性能
	 */
	public static void heapSort(int[] numbers){
		for(int i=0;i<numbers.length;i++){
			createMaxdHeap(numbers,numbers.length-1-i);
			swap(numbers,0,numbers.length-1-i);
			
		}
	}
	
	public static void swap(int[] numbers,int i,int j){
		if(i==j){
			return;
		}
		numbers[i]=numbers[i]+numbers[j];
		numbers[j]=numbers[i]-numbers[j];
		numbers[i]=numbers[i]-numbers[j];
	}
	
	public static void createMaxdHeap(int[] numbers,int lastIndex){
		for(int i=(lastIndex-1)/2;i>=0;i--){
			//保存当前正在你判断的节点
			int k=i;
			//若当前节点的子节点存在
			while(2*k+1<=lastIndex){
				//biggerIndex总是记录较大节点的值，先赋值为当前判断节点的左子节点
				int biggerIndex=2*k+1;
				if(biggerIndex<lastIndex){
					//若右子节点存在，否则此时biggerIndex应该等于lastIndex
					if(numbers[biggerIndex]<numbers[biggerIndex+1]){
						//若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值
						biggerIndex++;
					}
				}
				
				if(numbers[k]<numbers[biggerIndex]){
					//过当前节点值比子节点最大值小，则交换2者的值，交换后将biggerIndex值
					swap(numbers,k,biggerIndex);
					k=biggerIndex;
				}else{
					break;
				}
			}
		}
	}
	//sortUtil
	


}
